package Q3;

import java.util.LinkedList;
import java.util.Queue;

public class Solution {

    public int[] dx = {0, 0, 1, -1};
    public int[] dy = {1, -1, 0, 0};
    public int n;
    public int m;

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    public int solve (int[][] matrix) {
        // write code here

        n = matrix.length;
        m = matrix[0].length;

        int maxLen = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                maxLen = Math.max(maxLen, bfs(matrix, new int[]{i, j}, new boolean[n][m]));
            }
        }

        return maxLen;
    }

    public int bfs(int[][] matrix, int[] arr, boolean[][] flag) {
        int len = 0;

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(arr);
        while (!queue.isEmpty()) {
            int size = queue.size();
            len++;
            while (size > 0) {
                size--;
                int[] arr1 = queue.poll();
                int x = arr1[0];
                int y = arr1[1];
                flag[x][y] = true;
                for (int i = 0; i < 4; i++) {
                    int xx = x + dx[i];
                    int yy = y + dy[i];
                    if (xx >= 0 && xx < n && yy >= 0 && yy < m && !flag[xx][yy] && matrix[xx][yy] > matrix[x][y]) {
                        queue.offer(new int[]{xx, yy});
                        flag[xx][yy] = true;
                    }
                }
            }
        }

        return len;
    }
}